#include "operator.h"
#include "globals.h"
#include "bitset.h"
/* operator.c - operator precedence code.
 *
 * Apart from parsing input, most of the work related to creating the necessary
 * tables for operator precedence parsing is here.
 */

#define LEFT_HANDLE     (-1)
#define RIGHT_HANDLE    (1)
#define MIDDLE_HANDLE   (0)
#define ERROR_HANDLE    (-99)



/* TOpSym
 *
 * TOperator describes an operator, but an operator can comprise more
 * than one symbol. The operator precedence parser will be dealing with
 * individual symbols, as well most of the calculation we need to do
 * for constructing precedence functions. 
 */
typedef struct  TOpSym
    {
    TOperator*  Operator;       /* ptr to operator that contains this symbol    */
    int         ListIndex;      /* index of this symbol in the operator string  */
    int         OpSymVal;       /* operator symbols are numbered sequentially   */
    }           TOpSym;

static const char* OpSymStr(TOpSym* OpSym);

int*    FGTable;

static TOpSym**     OpSyms;
static int          NOpSyms;


static TOperator**  Operators;
static int          NOperators;

static int      NGroups;
static int      MaxGroups;
static int*     Groups;
static int      NFGSyms;
static int*     FGSyms;
static int      NEdges;
static int*     Edges;


void        OperatorFree(void)
    {
    int iOp;

    for(iOp=0; iOp < NOperators; ++iOp)
        {
        free((void*)Operators[iOp]->Pattern);
        SymbolListDestroy(Operators[iOp]->List);
        free(Operators[iOp]);
        }
    if(Operators)
        free(Operators);
    if(OpSyms)
        {
        for(iOp=0; iOp < NOpSyms; ++iOp)
            free(OpSyms[iOp]);
        free(OpSyms);
        }
//    if(FTable)
//        free(FTable);
//    if(GTable)
//        free(GTable);
//    if(Edges)
//        free(Edges);
    if(Groups)
        free(Groups);
    if(FGSyms)
        free(FGSyms);
    }

int     OpSymMatch(TOpSym* OpSym, const char* Pattern)
    {
    int     Result;
    char    Target[MAX_OPERATOR_PATTERN+1];

    strcpy(Target, OpSym->Operator->Pattern);
    Target[OpSym->ListIndex]    = '@';
    Result  = PatternCmp(Pattern, Target) >= 0;

//printf("OpSymMatch('%s', '%s') = %d\n", OpSymStr(OpSym), Pattern, Result);

    return Result;
    }

/* OpSymAdd() - try to add operator symbol to global list
 *
 * The complication is homonyms.
 */
TOpSym*     OpSymAdd(TOperator* Operator, int ListIndex)
    {
    TOpSym*     OpSym = NEW(TOpSym);

    assert(OpSym != NULL);
    OpSym->Operator     = Operator;
    OpSym->ListIndex    = ListIndex;
    OpSym->OpSymVal     = NOpSyms;
    ++NOpSyms;
    OpSyms              = (TOpSym**)realloc(OpSyms, sizeof(TOpSym*)*NOpSyms);
    assert(OpSyms != NULL);
    OpSyms[NOpSyms-1]   = OpSym;
    return OpSym;
    }

/* OperatorAdd_() - actual workhorse to add a new operator.
 *
 */
static
void OperatorAdd_(TToken Decl, int Precedence, int Associativity, SYMBOLS List, const char* Pattern)
    {
    int         iSymbol;
    TSymbol*    Symbol;
    TOperator*  Result  = NEW(TOperator);

    assert(Result != NULL);
    Result->Precedence      = Precedence;
    Result->Associativity   = Associativity;
    Result->List            = List;
    Result->Decl            = Decl;
    Result->Pattern         = StrClone(Pattern);

    ++NOperators;
    Result->IntRep          = NOperators;
    Operators               = (TOperator**)realloc(Operators, sizeof(TOperator*)*NOperators);
    assert(Operators != NULL);
    Operators[NOperators-1] = Result;

    for(iSymbol = 0; iSymbol < SymbolListCount(List); ++iSymbol)
        {
        Symbol  = SymbolListGet(List, iSymbol);
        if(Symbol)
            {
            OpSymAdd(Result, iSymbol);
            ++Result->SymCount;
            }
        }
    }

void  OperatorAdd(TToken Decl, int Precedence, int Associativity, SYMBOLS List, const char* Pattern)
    {
    static int      Initialized;

    /* We implicitly add the EOF token as an operator before any
     * other operators. It's an appropriate place to do so, since
     * $ is more or less the highest precedence operator (and higher
     * precedence is associated with operators defined earlier in
     * the BLACC input).
     */
    if(!Initialized)
        {
        TToken      Operand         = TokenFake(TK_IDENT, "<id>");
        TSymbol*    EofSym;
        TSymbol*    OperandSym;
        SYMBOLS     EofList         = NULL;
        SYMBOLS     OperandList     = NULL;

        EofSym  = SymbolFind(EOFToken);
        assert(EofSym != NULL);
        
        /* first, add the $ operator (our logical EOF) */
        EofList     = SymbolListAdd(EofList, SymbolFind(EOFToken));
        OperatorAdd_(EOFToken, 99999, TK_NONASSOC, EofList, ".");

        /* second, add the operand "operator"  */
        OperandSym  = SymbolAdd(Operand, SYM_TERMINAL);
        OperandList = SymbolListAdd(OperandList, OperandSym);
        OperatorAdd_(Operand, 0, TK_NONASSOC, OperandList, ".");

        Initialized     = TRUE;
        }
    OperatorAdd_(Decl, Precedence, Associativity, List, Pattern);
    }

TOperator*  OperatorGet(int Which)
    {
    TOperator*  Result  = NULL;

    assert(Which >= 0);
    if(Which < NOperators)
        Result  = Operators[Which];

    return Result;
    }

/*  OperatorCount() - global function to return total # of operators.
 */
int         OperatorCount(void)
    {
    return NOperators;
    }

/* OperatorFindOpSym() - Locate an operator that contains a given symbol.
 *
 * Sometimes an operator is simply a symbol, but sometimes it contains
 * multiple symbols. For example, searching for the operator symbol ')'
 * will match operators like "(X)", "X(X)", and "(X)X".
 */
TOperator*  OperatorFindOpSym(TOperator* Start, TSymbol* OpSym)
    {
    int         iOperator, iSymbol, NSymbols;
    TOperator*  Operator;

    iOperator   = 0;
    if(Start)
        for(; iOperator < NOperators; ++iOperator)
            if(Operators[iOperator] == Start)
                break;

    for(++iOperator; iOperator < NOperators; ++iOperator)
        {
        Operator    = Operators[iOperator];
        NSymbols    = SymbolListCount(Operator->List);
        for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
            if(SymbolListGet(Operator->List, iSymbol) == OpSym)
                return Operator;
        }

    return NULL;
    }

/*********************************************************************
 * code to calculate operator precedence tables.
 *********************************************************************/

#define GFLAG   0x8000

typedef struct  TGroup
    {
    int         iOpSym;
    int         iEdge;
    }           TGroup;



/* OpSymStr() - create human-readable string to identify operator symbol
 *
 * We need to print debug information about a particular symbol from
 * a particular operator.
 */
#define     MAX_SYM_STR (64)
static const char* OpSymStr(TOpSym* OpSym)
    {
    static char Buffer[256];
    static char*Rover = Buffer;
    char*       Result;
    SYMBOLS     List    = OpSym->Operator->List;
    int         iList;
    TSymbol*    Sym;

    assert(OpSym != NULL);
    if(Rover - Buffer > sizeof(Buffer)-MAX_SYM_STR)
        Rover   = Buffer;
    Rover[0]   = '\0';
    if(OpSym->Operator->SymCount > 1)
        {
        for(iList=0; iList < SymbolListCount(List); ++iList)
            {
            Sym     = SymbolListGet(List, iList);
            if(Sym == NULL)
                strcat(Rover, "X");
            else
                {
                TToken      Token   = LiteralFromSymbol(Sym);
                
                if(OpSym->ListIndex == iList)
                    strcat(Rover, "@");
                if(Token.Text == NULL)
                    Token   = Sym->Name;
                Token   = Unquote(Token);
                strncat(Rover, Token.Text, Token.TextLen);
                }
            }
        }
    else
        sprintf(Rover, "%.*s", OpSym->Operator->Decl.TextLen, OpSym->Operator->Decl.Text);

    Result  = Rover;
    Rover  += strlen(Rover)+1;

    return Result;
    }


/* CreateGroups() - partition our pseudo-symbols into groups.
 *
 * For each symbol (operator, operand, or $), we will create two
 * pseudo-symbols: call them the F and G versions of the original.
 *
 * We then partition them into groups, such that if a = b (= being
 * used in the precedence relation sense here), then Fa and Gb must
 * be in the same group.
 *
 * That's the general algorithm, but the specifics are much simpler
 * for BLACC. In effect, most operators do not have the = precedence
 * relation to each other, so each pseudo-operator simply goes in a
 * "group" by itself.
 *
 * The exceptions are multi-symbol operators like "()", "[]", and
 * "?:". For example, given the operator precedence specification of
 * "X?X:X", then ? and : will have a precedence relation of =.
 *
 * The fact that we do not allow the same symbol to be used in multiple
 * operators (except under a couple of well-defined situations) keeps
 * more complex cases from arising for the partitioning algorithm.
 *
 */


/* FromSameOperator() - do these tokens both appear in the same operator?
 */
static
int FromSameOperator(int OpTokA, int OpTokB)
    {
    int     Result  = TRUE;

    if(OpTokA != OpTokB)
        {
        if(OpTokA < 0 || OpTokA >= NOpSyms || OpTokB < 0 || OpTokB >= NOpSyms)
            Result  = FALSE;
        else
            Result  = (OpSyms[OpTokA]->Operator == OpSyms[OpTokB]->Operator);
        }

    return Result;
    }

/*                                                              
 * Groups:
 *     Groups is an integer array. Even elements in Groups
 * contain an offset into FGSyms, while odd elements contain
 * an offset into Edges (or -1). Conceptually, even elements
 * in Groups "point" to a sequence of one or more F/G symbols
 * in FGSyms that represent the one or more symbols in that group.
 */

static
void CreateGroups(void)
    {
    int         iFGSym, iOpSym;

    iFGSym  = 0;
    /* for each operator symbol (i.e., the "?:" operator contains 2 operator symbols)
     */
    for(iOpSym = 0; iOpSym < NOpSyms; ++iOpSym)
        {
        /* start new group with F(current symbol) */
        Groups[NGroups*2]   = iFGSym;
        Groups[NGroups*2+1] = -1;       /* no edges yet */
        ++NGroups;
        assert(NGroups <= MaxGroups);
        FGSyms[iFGSym++]    = iOpSym;

        /* if non-last symbol in a multi-symbol operator*/
        if(FromSameOperator(iOpSym, iOpSym+1))
            {
            /* add G(next symbol) to current group */
            FGSyms[iFGSym++]    = (iOpSym+1) | GFLAG;
            }
        /* if our G was already put in a previous group */
        if(FromSameOperator(iOpSym-1, iOpSym))
            ;
        /* else, our G gets its own group */
        else
            {
            Groups[NGroups*2]   = iFGSym;
            Groups[NGroups*2+1] = -1;       /* no edges yet */
            ++NGroups;
            assert(NGroups <= MaxGroups);
            FGSyms[iFGSym++]    = iOpSym | GFLAG;
            }
        }
    NFGSyms = iFGSym;
    if(Globals.Dump)
        {
        int     iGroup;

        printf("Groups:\n");
        for(iGroup=0; iGroup < NGroups; ++iGroup)
            {
            printf("    [%3d] ", iGroup);
            iFGSym  = Groups[iGroup*2];
            do
                {
                iOpSym  = FGSyms[iFGSym];
                printf("%c(%s) ", (iOpSym&GFLAG)?'G':'F', OpSymStr(OpSyms[iOpSym&~GFLAG]));
                ++iFGSym;
                } while(iFGSym < Groups[(iGroup+1)*2]);
            printf("\n");
            }
        }
    }

static
int LeftMostSym(int iOpSym, TOpSym* OpSym)
    {
    return  OpSym->Operator->SymCount > 1
        &&  !FromSameOperator(iOpSym, iOpSym-1);
    }
static
int RightMostSym(int iOpSym, TOpSym* OpSym)
    {
    return  OpSym->Operator->SymCount > 1
        &&  !FromSameOperator(iOpSym, iOpSym+1);
    }


/* LeftInterior() - is this left interior of multi-token operator?
 *
 * For example, is this the '[' in 'X[X]'? In this case, the '['
 * effectively has to compete for precedence with any operator to
 * the left.
 */
static int LeftInterior(int iOpSym, TOpSym* OpSym)
    {
    return OpSym->Operator->SymCount > 1            /* multisym operator */
        && OpSym->ListIndex != 0                    /* */
        && FromSameOperator(iOpSym, iOpSym+1);
    }

/* RightInterior() - is this right interior of multi-token operator?
 *
 * For example, is this the ')' in 'X(X)'? In this case, the ')'
 * effectively has to compete for precedence with any operator to 
 * the right.
 */
static int RightInterior(int iOpSym, TOpSym* OpSym)
    {
    return OpSym->Operator->SymCount > 1 && FromSameOperator(iOpSym-1, iOpSym);
    }

static int IsEnclosure(TOperator* Operator)
    {
    const char* Pattern = Operator->Pattern;
    size_t      Len     = strlen(Pattern);

    return Len >= 3
        && Pattern[0] == '.'
        && Pattern[strlen(Pattern)-1] == '.'
        ;
    }
/*  RightEnd() - is this the right-most symbol of a post-unary operator?
 */
static int RightEnd(TOpSym* OpSym)
    {
    int         Result;
    const char* Pattern = OpSym->Operator->Pattern;
    size_t      Len     = strlen(Pattern);

    Result= Len >= 2
        && Pattern[strlen(Pattern)-1] == '.'
        && OpSym->ListIndex == SymbolListCount(OpSym->Operator->List) - 1
        ;
#if 0 
printf("RightEnd(ListIndex=%d of %d, %s, %s) = %d\n",
       OpSym->ListIndex, SymbolListCount(OpSym->Operator->List), OpSymStr(OpSym), Pattern, Result);
#endif
return Result;
    }


/* LeftEnclosure() - is this a left enclosure of a multi-token operator?
 *
 * For example, is this the '(' in '(X)'? In this case, the '('
 * always identifies the start of a handle.
 */
static int LeftEnclosure(int iOpSym, TOpSym* OpSym)
    {
    return OpSym->Operator->SymCount > 1
        && !FromSameOperator(iOpSym-1, iOpSym)
        && OpSym->ListIndex == 0
    ;
    }

/* RightEnclosure() - is this a right enclosure of a multi-token operator?
 *
 * For example, is this the ')' in '(X)'? In this case, the ')'
 * always identifies the end of a handle.
 */
static int RightEnclosure(int iOpSym, TOpSym* OpSym)
    {
//fprintf(stdout, "RightEnclosure(%d)\n", iOpSym);
    return OpSym->Operator->SymCount > 1
        && !FromSameOperator(iOpSym, iOpSym+1)
        && OpSym->ListIndex == SymbolListCount(OpSym->Operator->List)-1
    ;
    }

static int FirstSymInOp(int iOpSym)
    {   return !FromSameOperator(iOpSym-1, iOpSym);   }

static int LastSymInOp(int iOpSym)
    {   return !FromSameOperator(iOpSym, iOpSym+1);   }

static
int PatCmp(const char* Pattern, TOpSym* OpSym)
    {
    size_t      Len;
    const char* Decl;

    Len     = OpSym->Operator->Decl.TextLen;
    Decl    = OpSym->Operator->Decl.Text;

    while(Len > 0 && *Pattern)
        {
        if(*Pattern == '.' && *Decl == 'X')
            break;
        else if(*Pattern == 'X' && *Decl != 'X')
            break;
        --Len;
        ++Pattern;
        ++Decl;
        }
    return Len <= 0 && *Pattern == '\0';
    }

static int OpRelationError(int iOpSymA, TOpSym* OpSymA, int iOpSymB, TOpSym* OpSymB)
    {
    int     Result  = FALSE;

    /* f$ <--> g$, no precedence relation (empty input not allowed) */
    if(iOpSymA == 0 && iOpSymB == 0)
        Result  = TRUE;
    /* f$ can't pop up in middle of multi-symbol operator */
    else if(FromSameOperator(iOpSymB-1, iOpSymB) && iOpSymA == 0)
        Result  = TRUE;
    /* g$ can't pop up in middle of multi-symbol operator */
    else if(FromSameOperator(iOpSymA, iOpSymA+1) && iOpSymB == 0)
        Result  = TRUE;
    /* LR(0) won't ask us, but <id> <id> is an error*/
    else if(iOpSymA == 1 && iOpSymB == 1)
        Result  = TRUE;
    /* left side is end of a grouping operator, right side must
     * not be id or prefix operator
     */
    else if (OpSymMatch(OpSymA, "X@$")        /* lhs is end of grouping op*/
         &&   (iOpSymB == 1                     /* rhs is <id>             */
            || OpSymMatch(OpSymB, "^@")         /* rhs is prefix operator  */
              )
            )
        Result  = TRUE;
    /* right side is start of a grouping operator, left side must
     * not be id or postfix operator
     */
    else if (OpSymMatch(OpSymB, "^@X")        /* rhs is end of grouping op    */
         &&   (iOpSymA == 1                     /* lhs is <id>                  */
            || OpSymMatch(OpSymB, "@$")         /* lhs is postfix operator      */
              )
            )
        Result  = TRUE;
#if 0
    /* postfix on left requires right bracket or EOF or binop on right */
    else if (OpSymMatch(OpSymA, "X*@$")
         && (iOpSymB != 0  )
            )
        Result = TRUE;
    /* LR(0) never inquires "precedence" of operand */
    else if(iOpSymA == 1 || iOpSymB == 1 || IsEnclosure(OpSymA->Operator) || IsEnclosure(OpSymB->Operator))
        Result  = TRUE;
    /* id id, no precedence relation    */
    else if(iOpSymA == 1 && iOpSymB == 1)
        Result  = TRUE;
/*??? probably not general enough*/
    /* id .X., no precedence relation  */
    else if(iOpSymA == 1 && PatCmp(".X.", OpSymB) && !FromSameOperator(iOpSymB-1, iOpSymB))
        Result  = TRUE;
    /* .X. id, no precedence relation  */
    else if(iOpSymB == 1 && PatCmp(".X.", OpSymA) && !FromSameOperator(iOpSymA, iOpSymA+1))
        Result  = TRUE;
#endif
    /* can't interleave two different distfix operators */
    else if(!FromSameOperator(iOpSymA, iOpSymB)
         && OpSymA->Operator->SymCount > 1
         && OpSymB->Operator->SymCount > 1
         && !
            (RightMostSym(iOpSymA, OpSymA) || LeftMostSym(iOpSymB, OpSymB))
           )
        Result  = TRUE;
    /* 2 symbols from same multi-symbol operator */
    else if(FromSameOperator(iOpSymA, iOpSymB) && OpSymA->Operator->SymCount > 1)
        {
        /* if in defined sequence */
        if(iOpSymA == iOpSymB-1)
            ;   /* then that's OK */
        /* if right-hand could represent start of nested operator */
        else if(FirstSymInOp(iOpSymB))
            ;   /* then that's OK */
        /* if left-hand could be end of nested operator*/
        else if(LastSymInOp(iOpSymA))
            ;   /* then that's OK */
        else
            Result  = TRUE;
        }
    return Result;
    }

static int AssertOp(int iOpSymA, int iOpSymB)
    {
    TOpSym*     OpSymA;
    TOpSym*     OpSymB;

    OpSymA      = OpSyms[iOpSymA];
    OpSymB      = OpSyms[iOpSymB];

    /* should be no grouping operators left at this point */
    if(OpSymMatch(OpSymA, "^.*.$") || OpSymMatch(OpSymB, "^.*.$"))
        assert(FALSE);
    /* better be looking at final opsym of left side */
    else if(!OpSymMatch(OpSymA, "@X?$"))
        assert(FALSE);
    /* better be looking at first opsym of right side */
    else if(!OpSymMatch(OpSymA, "X?@*$"))
        assert(FALSE);
    return FALSE;
    }

/* OpRelation() - return the operator precedence relation between two tokens.
 *
 * This is the function that embodies all our decisions about
 * what the precedence relations between tokens should be in order
 * to correctly implement the precedence and associativity that the
 * input grammar is asking for.
 */
static int OpRelation(int iOpSymA, int iOpSymB)
    {
    int         Result  = ERROR_HANDLE;
    int         RelChar;
    TOpSym*     OpSymA;
    TOpSym*     OpSymB;

    assert(iOpSymA >= 0); assert(iOpSymA < NOpSyms);
    assert(iOpSymB >= 0); assert(iOpSymB < NOpSyms);

    OpSymA      = OpSyms[iOpSymA];
    OpSymB      = OpSyms[iOpSymB];

    if(OpRelationError(iOpSymA, OpSymA, iOpSymB, OpSymB))
        ;
    else if(iOpSymA == 0)       /* $ on left */
        {
        if(iOpSymB == 1)        /* $ id */
            Result  = LEFT_HANDLE;
        else if(OpSymMatch(OpSymB, "^X@") || OpSymMatch(OpSymB, "^@"))
            Result  = LEFT_HANDLE;
        }
    else if(iOpSymB == 0)       /* $ on right */
        {
        if(iOpSymA == 1)        /* id $ */
            Result  = RIGHT_HANDLE;
        else if(OpSymMatch(OpSymA, "@X$") || OpSymMatch(OpSymA, "@$"))
            Result  = RIGHT_HANDLE;
        }
    else if(iOpSymA == 1)       /* id on left */
        {
        if(OpSymMatch(OpSymB, "X@"))
            Result  = RIGHT_HANDLE;
        }
    else if(iOpSymB == 1)       /* id on right */
        {
        if(OpSymMatch(OpSymA, "@X"))
            Result  = LEFT_HANDLE;
        }
    /* if it's two sequential tokens of a multi-token operator */
    else if(FromSameOperator(iOpSymA, iOpSymB) && iOpSymA+1 == iOpSymB)
        Result  = MIDDLE_HANDLE;
    else if(OpSymMatch(OpSymA, "@*."))    /* any kind of left bracketing opsym on left*/
        {
        Result  = LEFT_HANDLE;
        }
    else if(OpSymMatch(OpSymB, ".*@"))    /* any kind of right bracketing opsym on right*/
        {
        Result  = RIGHT_HANDLE;
        }
#if 0
    else if(OpSymMatch(OpSymA, "^.*@$"))    /* rightmost grouping opsym on left      */
        {
        if(OpSymMatch(OpSymB, ".*@"))
            Result  = RIGHT_HANDLE;
        }
#endif
#if 0
    else if(OpSymMatch(OpSymA, ".*@$"))    /* rightmost opsym in bracketing op on left*/
        {
        if(OpSymMatch(OpSymB, ".*@"))
            Result  = RIGHT_HANDLE;
        }
    /* else if there is an "operand" on one side or the other*/
    else if(iOpSymA == 1 || iOpSymB == 1)
        {
        /* these rules ensure any operand is reduced immediately */
        if(iOpSymA == 1)            /* id something     */
            Result  = RIGHT_HANDLE; /* id > all         */
        else if(iOpSymB == 1)       /* something id     */
            Result  = LEFT_HANDLE;  /* all < id         */
        }
    /* if left opsym can be viewed as rightmost sym of post-unary op */
//    else if(RightEnd(OpSymA))
    else if(OpSymMatch(OpSymA, "*X@$"))
        Result  = RIGHT_HANDLE;
//    else if(LeftMostSym(iOpSymA, OpSymA))
    else if(OpSymMatch(OpSymA, "^@X"))
//    LeftMostSym(iOpSymA, OpSymA))
        Result  = LEFT_HANDLE;
    else if(OpSymMatch(OpSymB, ".X@"))
//    else if(RightInterior(iOpSymB, OpSymB))
        Result  = RIGHT_HANDLE;
    else if(LeftEnclosure(iOpSymB, OpSymB))
        Result  = LEFT_HANDLE;
    else if(RightEnclosure(iOpSymA, OpSymA))
        Result  = RIGHT_HANDLE;
    else if(PatCmp(".X", OpSymB))   /* if right operator is unary prefix */
        Result  = LEFT_HANDLE;
    else if(PatCmp("X.", OpSymB))   /* if left operator is unary postfix */
        Result  = RIGHT_HANDLE;
#endif
    else if(AssertOp(iOpSymA, iOpSymB))
        assert(FALSE);
    else if(OpSymA->Operator->Precedence > OpSymB->Operator->Precedence)
        Result  = LEFT_HANDLE;
    else if(OpSymA->Operator->Precedence < OpSymB->Operator->Precedence)
        Result  = RIGHT_HANDLE;
    else    /* else, they have equal precedence */
        {
        if(OpSymA->Operator->Associativity == TK_LEFT)
            Result  = RIGHT_HANDLE;
        else if(OpSymA->Operator->Associativity == TK_RIGHT)
            Result  = LEFT_HANDLE;
        /* else it's non-associative, so leave it as an error */
        }

    switch(Result)
        {
        case LEFT_HANDLE:
            RelChar = '<';
            break;
        case RIGHT_HANDLE:
            RelChar = '>';
            break;
        case MIDDLE_HANDLE:
            RelChar = '=';
            break;
        default:
            RelChar = '?';
        }

    if(Globals.Verbose)
        {
        /* OpSymStr() overwrites previous result... */
        printf("    %s %c ", OpSymStr(OpSymA), RelChar);
        printf("%s\n", OpSymStr(OpSymB));
        }

    return Result;
    }

/* FindGroup() - locate the index of a group that contains the given pseudo-symbol
 */
static int  FindGroup(int PseudoSym)
    {
    int     iPseudoSym, iGroup;

    for(iPseudoSym = 0; FGSyms[iPseudoSym] != PseudoSym; ++iPseudoSym)
        assert(iPseudoSym < MaxGroups);
    assert(iPseudoSym < MaxGroups);
    for(iGroup = 0; iGroup < NGroups; ++iGroup)
        if(Groups[iGroup*2] > iPseudoSym)
            break;
    --iGroup;
    assert(iGroup >= 0);
    assert(iGroup < NGroups);

    return iGroup;
    }

/* AddEdge() - add an arrow from one group to another.
 *
 * Even indices into Edges contain the number of the group this
 * edge points to, while the next odd indice contains -1 (NIL)
 * or the offset of the next edge in the linked list of edges
 * for this group.
 */
static void AddEdge(int FGFrom, int FGTo)
    {
    int     FromGroup, ToGroup;
    int*    LinkPtr;
    int     iEdge;
    
    assert(FGFrom != FGTo);
    
    FromGroup   = FindGroup(FGFrom);
    ToGroup     = FindGroup(FGTo);
    LinkPtr     = &Groups[FromGroup*2 + 1];
    iEdge       = *LinkPtr;

    while(iEdge != -1)
        {
        assert(iEdge < NEdges);
        /* if the desired edge already exists*/
        if(Edges[iEdge*2] == FGTo)
            return;
        else
            {
            LinkPtr = &Edges[iEdge*2 + 1];
            iEdge   = *LinkPtr;
            }
        }
    /* do this before LinkPtr becomes invalid! */
    *LinkPtr            = NEdges;
    /* Add new link to end of linked list */
    Edges       = (int*)realloc(Edges, sizeof(int)*2*(NEdges+1));
    assert(Edges != NULL);
    Edges[NEdges*2]     = ToGroup;
    Edges[NEdges*2+1]   = -1;
    ++NEdges;

    if(Globals.Dump > 1)
        printf("edge from group %d -> %d (NEdges now %d)\n", FromGroup, ToGroup, NEdges);

#if 0
if(0)
    {
    for(iEdge = 0; iEdge < NEdges; ++iEdge)
        printf("[%d] ->%d, next=%d\n", iEdge, Edges[iEdge*2], Edges[iEdge*2+1]);
    }
#endif
    }

static void CreateEdges(void)
    {
    int OpSymA, OpSymB;
    
    for(OpSymA = 0; OpSymA < NOpSyms; ++OpSymA)
        for(OpSymB = 0; OpSymB < NOpSyms; ++OpSymB)
            {
            int     Relation = OpRelation(OpSymA, OpSymB);

#if 0
printf("Consider edge for (%s %c %s)\n",
       OpSymStr(OpSyms[OpSymA]),
       (Relation<0)?'<':((Relation>0)?'>':'?'),
       OpSymStr(OpSyms[OpSymB]));
#endif
            if(Relation == LEFT_HANDLE)
                AddEdge(OpSymB|GFLAG, OpSymA);
            else if(Relation == RIGHT_HANDLE)
                AddEdge(OpSymA, OpSymB|GFLAG);
            }
    }


typedef struct  TNode
    {
    int         Group;
    int         Edge;
    }           TNode;

/* GroupInStack() - does this group already exist on the stack?
 */
static
int  GroupInStack(TNode* Stack, int Max, int Group)
    {
    int iStack;
    
    for(iStack=0; iStack < Max; ++iStack)
        if(Stack[iStack].Group == Group)
            return TRUE;

    return FALSE;
    }

static int  FirstOfGroup(int iFGSym)
    {
    int     iGroup;
    int     Result  = FALSE;

    for(iGroup = 0; iGroup < NGroups; ++iGroup)
        if(Groups[iGroup*2] == iFGSym)
            {
            Result  = TRUE;
            break;
            }

    return Result;
    }


#if 0
static void DumpInternal(void)
    {
    int     iGroup, iFGSym, iEdge;

    printf("Groups:\n");
    for(iGroup=0; iGroup < NGroups; ++iGroup)
        printf("    [%3d] %3d %3d\n", iGroup, Groups[iGroup*2], Groups[iGroup*2+1]);
    printf("PseudoSymbols:\n");
    for(iFGSym = 0; iFGSym < MaxGroups; ++iFGSym)
        printf("    [%3d]%s0x%08X %s(%s)\n",
                iFGSym,
                (!FirstOfGroup(iFGSym)) ? "_" : " ",
                FGSyms[iFGSym],
               (FGSyms[iFGSym]&GFLAG)?"g":"f",
               OpSymStr(OpSyms[FGSyms[iFGSym]&~GFLAG])
             );
    printf("Edges:\n");
    for(iEdge = 0; iEdge < NEdges; ++iEdge)
        printf("    [%3d] Group(%3d) next->%3d\n", iEdge, Edges[iEdge*2], Edges[iEdge*2+1]);
    }

#endif

/* FindLongestPath() - 
 *
 *
 */
static
void    DumpStack(TNode* Stack, TNode* Node)
    {
    int     iOpSym;
    TNode*  Rover = Stack;

    printf("[%d] ", Node-Stack);
    do  {
#if 0
printf("Rover->Group=%d\n", Rover->Group);
fflush(stdout);
printf("Groups[Rover->Group*2]=%d\n", Groups[Rover->Group*2]);
fflush(stdout);
printf("FGSyms[Groups[Rover->Group*2]]=%d\n", FGSyms[Groups[Rover->Group*2]]);
fflush(stdout);
#endif
        iOpSym  = FGSyms[Groups[Rover->Group*2]];
        printf("%c%s", (iOpSym&GFLAG)?'g':'f',
               OpSymStr(OpSyms[iOpSym&~GFLAG]));
        } while(Rover++ != Node);

    printf("\n");
    }

#if 0
/* TopoOrder() - obtain a list of groups (vertices) in topological order
 */
static
int*     TopoOrder()
    {
    int*    Sorted;
    int*    Start;
    int     iSorted, iStart;
    int*    TmpEdges;
    int*    TmpGroups;

    /* make a copy of graph */
    TmpEdges    = malloc(sizeof(int)*2*NEdges);
    assert(TmpEdges != NULL);
    TmpGroups   = 
    /* Sorted will contain the nodes (group numbers) in topological order */
    Sorted      = calloc(NGroups, sizeof(Groups[0]));
    assert(Sorted != NULL);
    /* Start contains 0 or 1 to indicate with a node (group number) is in the list */
    Start       = calloc(NGroups, sizeof(Groups[0]));
    assert(Start != NULL);

    /* Start <- Set of all nodes with no incoming edges */
    /*     First, assume all nodes are start nodes      */
    for(iStart=0; iStart < NGroups; ++iStart)
        Start[iStart]   = 1;
    /*      Then eliminate the nodes that have incoming edges */
    for(iEdge = 0; iEdge < NEdges; ++iEdge)
        Start[Edges[iEdge*2]]   = 0;
    for(iSorted=0; ; ++iSorted)
        {
        /* locate the next node in Start */
        for(iStart = 0; iStart < NGroups; +iStart)
            if(Start[iStart])
                break;
        /* if no more nodes in Start, then we are done! */
        if(iStart >= NGroups)
            break;
        /* remove a node from Start and insert it into Sorted */
        Start[iStart]   = 0;
        Sorted[iSorted] = iStart;
        }

    }

/* FindLongestPath() - also does cycle detection!
 *
 * Algorithm stolen from Wikipedia. Brute force turns out to
 * be a looooooong wait when you have as many operators as C does.
 */
static
int FindLongestPath(int Group)
    {
    int     MaxPath = 0;
    int*    LengthTo;

    LengthTo    = calloc(NGroups, sizeof(int));
    assert(LengthTo != NULL);

    free(LengthTo);
    return MaxPath;
    }

static
int FindLongestPath(int Group)
    {
    int     HighWater;
    TNode*  Stack;
    TNode*  Node;

    Stack       = (TNode*)malloc(sizeof(TNode)*MaxGroups*2);
    assert(Stack != NULL);

    Node        = Stack;
//???    Node->Group = Groups[Group*2];
    Node->Group = Group;
    Node->Edge  = Groups[Group*2+1];
    HighWater   = 0;
printf("group=%d, MaxGroups=%d, Node->Group=%d\n", Group, MaxGroups, Node->Group);
    while(Node >= Stack)
        {
DumpStack(Stack, Node);
        /* if we hit end of linked list for this stacked node */
        if(Node->Edge == -1)
            {
            /* pop stack until we find a node not at end of its list */
            while(Node->Edge == -1 && Node >= Stack)
                --Node;
            }
        /* else, push the node pointed to by current edge */
        else
            {
            Group           = Edges[Node->Edge*2];
            if(GroupInStack(Stack, (Node-Stack)+1, Group))
                {
                int     iStack;
                TNode*  Rover = Stack;

                if(Globals.Dump)
                    {
                    DumpInternal();
                    for(iStack=0; Rover <= Node; ++iStack)
                        {
                        fprintf(stdout, "stack[%d] group = %d, edge = %d\n", iStack, Rover->Group, Rover->Edge);
                        ++Rover;
                        }
                    }
                ErrorExit(ERROR_FAILED_OP_PREC_TABLE,
                      "Internal error(FindLongestPath() cycle via %d\n"
                      "Can't create operator precedence table.\n",
                      Group
                      );
                }
            /* ??? is this off by one?*/
            assert(Node-Stack < MaxGroups*2);
            Node[1].Group   = Group;
            Node[1].Edge    = Groups[Group*2+1];
printf("push group=%d, Edge=%d\n", Group, Groups[Group*2+1]);
            /* but first advance in linked list of current topmost node */
            Node->Edge      = Edges[Node->Edge*2+1];
printf("    previous edge moves to %d\n", Node->Edge);
            ++Node;
            }

        if(Node-Stack > HighWater)
            HighWater   = Node-Stack;
        }

printf("HighWater was %d\n", HighWater);
    free(Stack);
    
    return HighWater;
    }

#endif
/* CalcPrec() - calculate the precedence table, if possible.
 *
 * The algorithm is taken from:
 *     "A Note on Computing Precedence Functions",
 *     The Computer Journal
 *     Vol 25, No. 3, 1982
 *     pp. 397-398
 * Note that, due to the restricted method we offer for specifying
 * operator precedence, we don't have to worry about the '=' relation
 * here.
 */
static
void CalcPrec(void)
    {
    int         iOpSym, iOpSymA, iOpSymB, iPrec, iNode;
    BITSET*     Links;
    BITSET*     EqLinks;
    BITSET      Nodes;
    BITITER     Node;
    
    /* create space to represent our reversed graph */
    Links   = malloc(2*sizeof(BITSET)*2*NOpSyms);
    assert(Links != NULL);

    for(iNode=0; iNode < 2*2*NOpSyms; ++iNode)
        Links[iNode]    = BitSetNew(2*NOpSyms);
    EqLinks = Links + 2*NOpSyms;

    /* Create representation of backward operator precedence graph. */
    for(iOpSymA = 0; iOpSymA < NOpSyms; ++iOpSymA)
        for(iOpSymB = 0; iOpSymB < NOpSyms; ++iOpSymB)
            {
            int     Rel = OpRelation(iOpSymA, iOpSymB);

            if(Rel == RIGHT_HANDLE)         /* fA > gB, so make gB -> fA            */
                BitSetSet(Links[NOpSyms + iOpSymB], iOpSymA);
            else if(Rel == LEFT_HANDLE)     /* fA < gB, so make fA -> gB            */
                BitSetSet(Links[iOpSymA], NOpSyms+iOpSymB);
//            else if(Rel == MIDDLE_HANDLE)   /* fA = gB, so make gB -- fA*/
//                BitSetSet(EqLinks[NOpSyms+iOpSymB], iOpSymA);
            }
    for(iOpSymA = 0; iOpSymA < NOpSyms; ++iOpSymA)
        {
        TOpSym*     OpSym = OpSyms[iOpSymA];
        
        if(LeftMostSym(iOpSymA, OpSym))
            {
            for(iOpSymB=iOpSymA+1; FromSameOperator(iOpSymA, iOpSymB); ++iOpSymB)
                {
                BitSetSet(EqLinks[iOpSymA], iOpSymB+NOpSyms);
                BitSetSet(EqLinks[NOpSyms+iOpSymB], iOpSymA);
                }
            }
        }

    /* Finally, we can start calculating precedences.
     * Start with f$ and g$ and trace the backwards graph from there.
     */
    /* create f and g tables, assume everything zero precedence initially */
    FGTable      = (int*)calloc(NOpSyms*2, sizeof(int));
    assert(FGTable != NULL);

    Nodes   = BitSetNew(NOpSyms*2);
    /* set initial set of nodes */
    BitSetSet(Nodes, 0);
    BitSetSet(Nodes, NOpSyms);
#if 0
    for(iOpSym = 1; iOpSym < NOpSyms; ++iOpSym)
        {
        TOpSym*     OpSym = OpSyms[iOpSym];

        if(OpSym->Operator->SymCount > 1)   /* if multisymbol operator */
            {
            /* if leftmost opsym with no operand to left */
            if(OpSym->ListIndex == 0)
                {
                BitSetSet(Nodes, iOpSym);
                BitSetOr(Nodes, EqLinks[iOpSym]);
                }
            /* if rightmost opsym with no operand to right */
            else if(OpSym->ListIndex == SymbolListCount(OpSym->Operator->List)-1)
                {
                BitSetSet(Nodes, iOpSym + NOpSyms);
                BitSetOr(Nodes, EqLinks[iOpSym+NOpSyms]);
                }
            }
        }
#endif
    for(iPrec = 0; iPrec < 2*NOpSyms && BitSetCount(Nodes); ++iPrec)
        {
        int     iOpSym;
        BITSET  Next;

        if(Globals.Dump && Globals.Verbose)
            {
            printf("[%d] ", iPrec);
            Node    = BitIterNew(Nodes);
            while((iOpSym=BitIterNext(&Node)) != -1)
                {
                int G=(iOpSym >= NOpSyms);
                
                printf("%c%s ", G?'g':'f', OpSymStr(OpSyms[G?iOpSym-NOpSyms:iOpSym]));
                }
            printf("\n");
            fflush(stdout);
            }
        Next    = BitSetNew(2*NOpSyms); /* Next will contain the next set of nodes */

        /* for all nodes in this step of traversal */
        Node    = BitIterNew(Nodes);
        while((iOpSym=BitIterNext(&Node)) != -1)
            {
//            BITITER Temp;
{
BITITER Temp;
char    FG;

FG  = (iOpSym / NOpSyms)?'g':'f';

printf("%c%s -> ", FG, OpSymStr(OpSyms[iOpSym%NOpSyms]));
Temp    = BitIterNew(Links[iOpSym]);
while((iOpSymA=BitIterNext(&Temp)) != -1)
    {
    FG  = (iOpSymA / NOpSyms)?'g':'f';
    printf("%c%s ", FG, OpSymStr(OpSyms[iOpSymA%NOpSyms]));
    }
printf("\n    ===> ");
Temp    = BitIterNew(EqLinks[iOpSym]);
while((iOpSymA=BitIterNext(&Temp)) != -1)
    {
    FG  = (iOpSymA / NOpSyms)?'g':'f';
    printf("%c%s ", FG, OpSymStr(OpSyms[iOpSymA%NOpSyms]));
    }
printf("\n");
}
            /* put it in our next set of nodes */
            BitSetOr(Next, Links[iOpSym]);
            BitSetOr(Next, EqLinks[iOpSym]);
            }

        /* update precedence numbers for next set of nodes */
        Node    = BitIterNew(Next);
        while((iOpSym=BitIterNext(&Node)) != -1)
            if(FGTable[iOpSym] <= iPrec)
                FGTable[iOpSym] = iPrec + 1;

        BitSetCopy(Nodes, Next);
        BitSetDelete(Next);
        }
    if(iPrec >= 2*NOpSyms)
        ErrorExit(ERROR_FAILED_OP_PREC_TABLE, "Can't happen: Could not create operator precedence table!");

    if(Globals.Dump)
        {
        printf("f/g table for %d operator symbols!\n", NOpSyms);
        for(iOpSym = 0; iOpSym < NOpSyms; ++iOpSym)
            printf("%10s [%3d] f%3d g%3d\n",
                   OpSymStr(OpSyms[iOpSym]),
                   iOpSym, FGTable[iOpSym], FGTable[NOpSyms+iOpSym]);
        fflush(stdout);
        }
    /* Now double-check FTable and GTable. We take the Cartesian
     * product of all the operator tokens and, for each pair,
     * confirm that FTable and GTable provide the same precedence
     * relation as OpRelation() claims it should.
     */
    for(iOpSymA = 0; iOpSymA < NOpSyms; ++iOpSymA)
        for(iOpSymB = 0; iOpSymB < NOpSyms; ++iOpSymB)
            {
            int     Rel = OpRelation(iOpSymA, iOpSymB);

            if(Rel != ERROR_HANDLE)
                {
                int     Disaster = FALSE;
                
                if(Rel == LEFT_HANDLE && FGTable[iOpSymA] >= FGTable[NOpSyms+iOpSymB])
                    Disaster    = TRUE;
                else if(Rel == RIGHT_HANDLE && FGTable[iOpSymA] <= FGTable[NOpSyms+iOpSymB])
                    Disaster    = TRUE;
                else if(Rel == MIDDLE_HANDLE && FGTable[iOpSymA] != FGTable[NOpSyms+iOpSymB])
                    Disaster    = TRUE;
                if(Disaster)
                    {
                    fprintf(stderr, "Can't happen: f(%d) g(%d)\n"
                            "OpRelation()=%d f(%s) = %d g(%s) = %d\n",
                            iOpSymA, iOpSymB,
                            Rel, OpSymStr(OpSyms[iOpSymA]), FGTable[iOpSymA],
                            OpSymStr(OpSyms[iOpSymB]), FGTable[NOpSyms+iOpSymB]);
                    ErrorExit(ERROR_FAILED_OP_PREC_TABLE, "Can't happen: Could not create correct operator precedence table!");
                    }
                }
            }
    }

#if 0
/* CalcPrec() - calculate precedence tables.
 *
 * CalcPrec
 *     FindGroup()
 *     FindLongestPath()
 *         GroupInStack()
 */
static void CalcPrec(void)
    {
    int     iOpSym, iOpSymA, iOpSymB;
    
    FTable      = (int*)malloc(sizeof(int)*NOpSyms);
    assert(FTable != NULL);
    GTable      = (int*)malloc(sizeof(int)*NOpSyms);
    assert(GTable != NULL);

    if(Globals.Dump)
        {
        DumpInternal();
        printf("f/g table for %d operator symbols!\n", NOpSyms);
        }
    for(iOpSym = 0; iOpSym < NOpSyms; ++iOpSym)
        {
        FTable[iOpSym]  = FindLongestPath(FindGroup(iOpSym));
        GTable[iOpSym]  = FindLongestPath(FindGroup(iOpSym|GFLAG));

        if(Globals.Dump)
            printf("%6s [%3d] f%3d g%3d\n",
               OpSymStr(OpSyms[iOpSym]),
               iOpSym, FTable[iOpSym], GTable[iOpSym]);

        }
    /* Now double-check FTable and GTable. We take the Cartesian
     * product of all the operator tokens and, for each pair,
     * confirm that FTable and GTable provide the same precedence
     * relation as OpRelation() claims it should.
     */
    
    for(iOpSymA = 0; iOpSymA < NOpSyms; ++iOpSymA)
        for(iOpSymB = 0; iOpSymB < NOpSyms; ++iOpSymB)
            {
            int     Rel = OpRelation(iOpSymA, iOpSymB);

            if(Rel != ERROR_HANDLE)
                {
                int     Disaster = FALSE;
                
                if(Rel == -1 && FTable[iOpSymA] >= GTable[iOpSymB])
                    Disaster    = TRUE;
                else if(Rel == 1 && FTable[iOpSymA] <= GTable[iOpSymB])
                    Disaster    = TRUE;
                else if(Rel == 0 && FTable[iOpSymA] != GTable[iOpSymB])
                    Disaster    = TRUE;
                if(Disaster)
                    {//??? need official error code
                    fprintf(stderr, "Can't happen: f(%d) g(%d)\n"
                            "OpRelation()=%d f(%s) = %d g(%s) = %d\n",
                            iOpSymA, iOpSymB,
                            Rel, OpSymStr(OpSyms[iOpSymA]), FTable[iOpSymA],
                            OpSymStr(OpSyms[iOpSymB]), GTable[iOpSymB]);
DumpInternal();
                    exit(-999);
                    }
                }
            }
    }

#endif
/* OperatorCalcPrec() - calculate precedence function tables.
 *
 * Here is where we calculate the precedence function tables
 * FTable and GTable -- abbreviated forms of the complete operator
 * precedence matrix.
 */
void        OperatorCalcPrec(void)
    {
    if(NOpSyms > 0)
        {
        MaxGroups   = NOpSyms * 2;  /* that's the worst case # of groups required ??? */
        Groups      = (int*)malloc(sizeof(int)*MaxGroups*2);
        assert(Groups != NULL);
        FGSyms      = (int*)malloc(sizeof(int)*MaxGroups);
        if(Globals.Dump)
            printf("    CalcPrec\n");
        CalcPrec();
        }
    }
